package 中等.队列;


/**
 * 给你一个下标从 0 开始的整数数组 nums 和一个正整数 k 。
 * 你可以对数组执行下述操作 任意次 ：
 * 从数组中选出长度为 k 的 任一 子数组，并将子数组中每个元素都 减去 1 。
 * 如果你可以使数组中的所有元素都等于 0 ，返回  true ；否则，返回 false 。
 * 子数组 是数组中的一个非空连续元素序列。
 *
 * @ https://leetcode.cn/problems/apply-operations-to-make-all-array-elements-equal-to-zero/description/
 * @date 2024/08/24
 */
public class 使数组中的所有元素都等于零_2772 {

    public static void main(String[] args) {

        System.out.println(checkArray(new int[]{1, 3, 1, 1}, 2));

    }

    /**
     * 差分数组
     * 如果想要 nums[0] 变成 0 ，那么必须以 nums[0] 开头的k长度字数组元素
     * 都 -nums[0]
     * 如果 nums[1] - nums[1] < 0，那么不能满足所有元素 = 0
     */
    public static boolean checkArray(int[] nums, int k) {
        int[] diff = new int[nums.length + 1];

        int preDiffSum = 0;
        for (int i = 0; i <= nums.length - k; i++) {
            int curNum = nums[i] + preDiffSum + diff[i];

            if (curNum < 0) {
                return false;
            }

            diff[i] -= curNum;
            preDiffSum += diff[i];
            diff[i + k] += curNum;
        }

        // 最后 k-1 个元素，没有 k 个连续子串，不能再 -1 了
        for (int i = nums.length - k + 1; i < nums.length; i++) {

            if (nums[i] + preDiffSum + diff[i] != 0) {
                return false;
            }
            preDiffSum += diff[i];

        }
        return true;
    }

}
